#include <bits/stdc++.h>
using namespace std;

/*
2411. 按位或最大的最小子数组长度
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。
一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

 

示例 1：

输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。
- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
所以我们返回 [3,3,2,2,1] 。
示例 2：

输入：nums = [1,2]
输出：[2,1]
解释：
下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。
 

提示：

n == nums.length
1 <= n <= 10^5
0 <= nums[i] <= 10^9
*/

// 法一
class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        // 每个二进制位最后出现的位置
        unordered_map<int, int> lastPos;

        for (int i = n - 1; i >= 0; i--) {
            // update lastPos
            int num = nums[i];
            // 1 <= n <= 10^5 --> 32
            for (int j = 0; j < 32; j++) {
                if (num >> j & 1)   lastPos[j] = i;
            }

            // 当前位置i的最短子数组长度
            int maxLast = i;
            for (const auto& pair : lastPos)    maxLast = max(maxLast, pair.second);
            ans[i] = maxLast - i + 1;
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        // 初始化答案数组，默认每个位置的最小长度为1（即子数组仅包含自身）
        vector<int> ans(n, 1);
        // 记录每个二进制位（0-29位）最后一次出现的位置，初始化为-1表示未出现
        vector<int> last_occur(30, -1);

        // 从后向前遍历数组（逆序是关键）
        for (int i = n - 1; i >= 0; --i) {
            int max_end = i; // 当前起始点i对应的子数组最大结束位置，默认为i（即子数组长度为1）
            
            // 遍历30个二进制位（因 nums[i] ≤ 10^9 < 2^30）
            for (int bit = 0; bit < 30; ++bit) {
                // 若当前数字的bit位为1，更新该位最后一次出现位置为i
                if ((nums[i] >> bit) & 1) {
                    last_occur[bit] = i;
                } 
                // 若该位曾在i之后出现过，用其位置更新最大结束位置
                else if (last_occur[bit] != -1) {
                    max_end = max(max_end, last_occur[bit]);
                }
            }
            
            // 计算以i起始的最短子数组长度
            ans[i] = max_end - i + 1;
        }
        return ans;
    }
};

// 法三
class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        // 滑动窗口 性能在面对大数据量时 表现更佳
        // 滑动窗口 + 单调栈
        int n = nums.size();
        vector<int> ans(n);
        ans[n - 1] = 1; // 最后一个元素的最短子数组长度显然为1
        if (n == 1)     return ans;
      
        // prepare 倒数第二个的或 更新为本身与最后一个元素的或
        // 栈中至少两个元素 便于判断窗口右侧指针的移动  窗口边界的滑动
        nums[n - 1] |= nums[n - 2];

        // 所需结构
        int left_or = 0, right = n - 1, bottom = n - 2;
        // 右往左遍历 每一个位置都作为左边界
        for (int left = n - 2; left >= 0; left--) {
            left_or |= nums[left];      // 更新左边界累加的或

            // 判断右端是否可以向左收缩
            // -->收缩后子数组或不变 就可以收缩进行下一步 得到更短的子数组
            while (right > left && (left_or | nums[right]) == (left_or | nums[right - 1])) {
                right--;
                // 检测栈结构
                if (bottom >= right) {
                    // 重建单调栈
                    for (int i = left + 1; i <= right; i++)     nums[i] |= nums[i - 1];

                    // 重新给栈底
                    bottom = left;
                    left_or = 0;        // 重建单调栈之后 累计或也要重置
                }
            }
            // 记录当前的最短子数组的len
            ans[left] = right - left + 1;
        }
        return ans;
    }
};